// trie tree: 字典树（前缀树、后缀树、单词查找树）
// 定义：字符串从左到右，根据每个字符的位置，将其存放到对应的树节点下，用节点中的某个信息表示单词到此结束
// 特点：字典树利用了字符串的公共前缀，节约了存储字符串的空间，提升了在集合中查找字符串的效率
// 场景：保存大量字符串、字符串统计、匹配

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 字典树的三个主要操作就是insert、search和startsWith
// 下面实现字典树（字符串中仅包含小写字母，如果其他情况，将节点中的数组改成hash表）
class TrieNode
{
public:
    TrieNode() : isWord(false), children(new TrieNode*[26])
    {
    }

    ~TrieNode()
    {
        if(children)
            delete[] children;
    }
    bool isWord; // 表示单词到此节点是否结束
    TrieNode** children; // 数组，利用数组下标代表字符a~z
};


class TrieTree
{
public:
    TrieTree() : root(new TrieNode)
    {}

    // 插入元素
    void insert(const string& s) const
    {
        TrieNode* cur = root;
        for(auto& ch : s) // 依次遍历字符串，在字典树中搜索，如果没有搜索到当前字符，就新增下层节点，找到则继续往下找
        {
            int index = ch-'a';
            if(cur->children[index] == nullptr) // 空，表明要创建节点
                cur->children[index] = new TrieNode;
            cur = cur->children[index];
        }
        cur->isWord = true;
    }

    // 在字典树中匹配字符串，要完全匹配
    bool search(const string& s) const
    {
        TrieNode* cur = root;
        for(auto& ch : s)
        {
            int index = ch - 'a';
            if(cur->children[index] == nullptr)
                return false;
            cur = cur->children[index];
        }
        return cur->isWord;
    }


    // 判断字符串是否是字典树的前缀
    bool startsWith(const string& s) const
    {
        TrieNode* cur = root;
        for(auto& ch : s)
        {
            int index = ch - 'a';
            if(cur->children[index] == nullptr)
                return false;
            cur = cur->children[index];
        }
        return true;
    }

    // 判断字典树是否是字符串的前缀
    bool isPrefix(const string& s) const
    {
        TrieNode* cur = root;
        for(auto& ch : s)
        {
            int index = ch - 'a';
            if(cur->isWord) return true;
            if(cur->children[index] == nullptr) return false;
            cur = cur->children[index];
        }
        return cur->isWord;
    }

private:
    TrieNode* root;
};

void createTrieTree(const TrieTree& t, vector<string>& vStrs)
{
    for(auto& str : vStrs)
        t.insert(str);
}

void searchTrieTree(const TrieTree& t, vector<string>& vStrs)
{
    for(auto& str : vStrs)
    {
        if(t.search(str))
            cout << "true" << " ";
        else
            cout << "false" << " ";
    }
    cout << endl;
}

void satwithTrieTree(const TrieTree& t, vector<string>& vStrs)
{
    for(auto& str : vStrs)
    {
        if(t.startsWith(str))
            cout << "true" << " ";
        else
            cout << "false" << " ";
    }
    cout << endl;
}

void pfixTrieTree(const TrieTree& t, vector<string>& vStrs)
{
    for(auto& str : vStrs)
    {
        if(t.isPrefix(str))
            cout << "true" << " ";
        else
            cout << "false" << " ";
    }
    cout << endl;
}

int main()
{
    vector<string> insrt = {"catch", "cat", "dog", "done", "hi"};
    vector<string> serch = {"catch", "catchcat", "nihao", "do", "c"}; // true false false false false(完全匹配)
    vector<string> satwith = {"catc", "c", "dogg"}; // true true false（字符串是否是字典树的前缀）
    vector<string> pfix = {"catchcat", "doog", "c"}; // true false false（字典树是否是字符串的前缀）

    TrieTree t;
    
    createTrieTree(t, insrt);

    searchTrieTree(t, serch);

    satwithTrieTree(t, satwith);

    pfixTrieTree(t, pfix);

    return 0;
}